プローブシーケンス（probe sequence）
ハッシュ値を配列のインデクスに使うときの方式（インデクスの生成方法）のこと
「プローブシーケンス」とは通常、ハッシュテーブルの検索中に実行される一連のステップを指します。 新しい要素を挿入するとき、またはハッシュテーブル内の既存の要素を検索するとき、ハッシュ関数を使用して、要素をハッシュテーブルを紐付ける配列内のインデックスにマップする。
ただし、異なる要素が同じインデックスにハッシュされる可能性があるため (ハッシュの衝突)、何らかの形式の衝突解決戦略が必要です。
これらの戦略によってチェックされる位置のシーケンスを「プローブシーケンス」と呼ぶ。
table:プローブシーケンスの種類
名前 インデックス衝突時の解決方法
Linear probing 空きスロットが見つかるまでテーブルが線形に (たとえば一度に 1 つのインデックスずつ) プローブする。末尾まで行ったら先頭に戻って検索する。
Quadratic probing ハッシュテーブル内を直線的に移動するのではなく、プローブ間の間隔が二次関数的に増加する
たとえば、インデックス 1、4、9、16... などの位置をプローブする
Double hashing 2つ目のハッシュ関数を使用してプローブの間隔を決める。
これは線形および二次プロービングでよくある問題であるクラスタリングを防ぐのに役立つ。
線形プローブ
キャッシュに優しい
配列を直接メモリ順に並んで操作するのでCPUキャッシュに乗りやすい
悪い点はクラスタリングが起こること
一部のメモリ空間上にバケットが溜まりやすくなる